class Solution:
    def shortestPathBinaryMatrix(self, grid: list) -> int:
        def nextPos(x, y, grid):
            length = len(grid[0]) - 1
            width = len(grid) - 1
            res = []
            if y - 1 >= 0 and grid[x][y - 1] == 0:
                res.append((x, y - 1))
            if y + 1 <= width and grid[x][y + 1] == 0:
                res.append((x, y + 1))
            if x - 1 >= 0 and grid[x - 1][y] == 0:
                res.append((x - 1, y))
            if x + 1 <= length and grid[x + 1][y] == 0:
                res.append((x + 1, y))
            if y - 1 >= 0 and x - 1 >= 0 and grid[x - 1][y - 1] == 0:
                res.append((x - 1, y - 1))
            if y + 1 <= width and x - 1 >= 0 and grid[x - 1][y + 1] == 0:
                res.append((x - 1, y + 1))
            if y - 1 >= 0 and x + 1 <= length and grid[x + 1][y - 1] == 0:
                res.append((x + 1, y - 1))
            if y + 1 <= width and x + 1 <= length and grid[x + 1][y + 1] == 0:
                res.append((x + 1, y + 1))
            return res
        if grid[0][0] == 1:
            return -1
        ans = 0
        queue = [(0, 0)]
        visited = set()
        visited.add((0, 0))
        while queue:
            ans += 1
            for _ in range(len(queue)):
                x, y = queue.pop(0)
                if x == len(grid[0]) - 1 and y == len(grid) - 1:
                    return ans
                for nx, ny in nextPos(x, y, grid):
                    if (nx, ny) in visited:
                        continue
                    queue.append((nx, ny))
                    visited.add((nx, ny))
        return -1
